import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-07-31
 * Time: 18:03
 */
class Solution25 {
    public int maxEnvelopes(int[][] envelopes) {
        // 解法二 重写排序+贪心+二分
        int n = envelopes.length;
        //按照左端点排序 分类
        Arrays.sort(envelopes,(v1,v2)->{
            if(v1[0] != v2[0]) {
                return v1[0]-v2[0];
            }else {
                return v2[1]-v1[1];
            }
        });

        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(envelopes[0][1]);

        for(int i = 1; i < n; i++) {
            int b = envelopes[i][1];
            if(b > ret.get(ret.size()-1)) {
                ret.add(b);
            }else {
                // 二分
                int left = 0,right = ret.size()-1;
                while(left < right) {
                    int mid = (left+right)/2;
                    if(ret.get(mid) >= b) {
                        right = mid;
                    }else {
                        left = mid+1;
                    }
                }
                ret.set(left,b);
            }
        }
        return ret.size();
    }
}

//    // 解法一动规,在这里会超时
//    public int maxEnvelopes(int[][] envelopes) {
//        int n = envelopes.length;
//        //按照左端点排序
//        Arrays.sort(envelopes,(v1, v2)->{
//            return v1[0]-v2[0];
//        });
//
//        //1.dp[i]表示 以第i个下标结束最大套娃的个数
//        int[] dp = new int[n];
//        //2.初始化
//        Arrays.fill(dp,1);
//        int ret = 0;
//        for(int i = 0; i < n; i++) {
//            int a = envelopes[i][0],b = envelopes[i][1];
//            for(int j = 0; j <= i; j++) {
//                if(envelopes[j][0] < a && envelopes[j][1] < b) {
//                    dp[i] = Math.max(dp[i],dp[j]+1);
//                }
//            }
//            ret = Math.max(dp[i],ret);
//        }
//        return ret;
//    }
